//
//  并查集3.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/2.
//

import UIKit
// 优化QU
class UnionFind_QU_S: UnionFind_QU {
    var sizes: [Int]
    override init(_ length: Int) {
        sizes = Array(repeating: 1, count: length)
        super.init(length)
    }
    
    /// 合并（节点少的，合并到节点多的节点上）
    /// - Parameters:
    ///   - v1: 1
    ///   - v2: 2
    override func union(_ v1: Int, _ v2: Int) {
        let p1 = find(v1)
        let p2 = find(v2)
        if p1 == p2 {
            return
        }
        if sizes[p1] < sizes[p2] {
            parents[p1] = p2
            sizes[p2] += sizes[p1]
        } else {
            parents[p2] = p1
            sizes[p1] += sizes[p2]
        }
    }
}
